A network that allows two or more devices (or terminals) to link up spontaneously to conduct mutual communication is called an ad-hoc wireless network, or a multi-hop wireless network. Such a network does not require a specific control station, and the devices define a self-organized local network by themselves. In an ad hoc wireless network, terminals that cannot communicate directly with each other can transmit and receive packets via a third terminal located between them, while keeping the transmit power levels low. The communication range can be expanded with this arrangement. In fact, network layer routing protocols are proposed as the Internet standard of the ad hoc wireless network. See, for example, S. Corson and J. Macker, “Mobile Ad hoc Networking (MANET): Routing Protocol Performance Issues and Evaluation Considerations”, Internet standard RFC 2501, January 1999.
On the other hand, in a wired network, packets are transmitted between different network segments using bridges, and a packet transmission technique based on a spanning tree protocol is known. See, for example, “Information Technology, Telecommunications and Information Exchange between Systems, Local Area Networks, Media Access Control (MAC) Bridges”, ISO/IEC 10038, ANSI/IEEE Std 802. ID, 1993. With this technique, a specific bridge or basestation is selected as a root bridge, and a transmission tree extending from the root bridge is created using a spanning tree protocol to prevent a loop and realize a fault-tolerant system.
An example of the transmission tree in a wired network is illustrated in FIG. 1. Bridge 1 is selected as a root bridge, and a nonloop transmission tree is created from the root bridge. The nodes to which packets are transmitted are recorded in a learning table, in association with the radio interfaces.
In order to apply the above-described packet transmission technique using wired bridges to a wireless network, multiple wireless interfaces have to be provided to each of the nodes through which packets are transmitted. This attempt further requires an antenna and a modulation and demodulation circuit to be added to each of the interfaces; and is disadvantageous on the cost front.
To overcome this problem, JP 2000-69046A proposes a technique for virtually providing multiple wireless interfaces by regarding the address of the correspondent node as a virtual interface. This method allows the concept of wired network spanning tree to be applied to packet transmission in a wireless network, using substantially a single wireless interface. Each of the wireless basestations is furnished with an address table, in which table the address of the correspondent node is recorded in association with the next node to which the packet is to be transmitted.
Another publication JP 2000-78147A discloses a technique for reducing redundancy of packet transmission routes, making use of the feature of wireless communications, that is, the fact that packets can reach a wireless station as long as that wireless station is located within the communication range, even if the station is not the correspondent node. With this technique, each wireless station monitors packets approaching that station along a tree-like transmission route. A table is created to record the source device indicated by the source address contained in the packet, in association with the previous wireless node (or basestation) indicated by the address of the transmitting station. Using the table, a shorter route can be selected in packet transmission.
Still another publication JP 2003-188811 proposes a method for improving the communication quality by determining whether the power level of the signal received from a basestation is at or above a threshold level when creating a transmission tree, and by not establishing a link if the detected power level is below the threshold.
By the way, it is necessary for an ad hoc wireless network to select the optimum route in a short time when transmitting packets or creating a transmission tree if such a tree is used. However, in wireless communication channels, the network environment and conditions are likely to change, as compared with wired communication channels. Accordingly, JP 2003-152786A proposes to introduce a weighting value reflecting the bit error rate and the transmission rate between adjacent wireless devices (or wireless basestations) in determining the optimum route. The weighting values set in the links between adjacent devices are successively added up to determine the optimum route.
The packet transmission routing protocol proposed by the above-described Internet Standard RFC 2501 requires all the devices forming the network to be furnished with packet relay functions. In other words, devices with less sophisticated functions cannot participate in the network, and extra funds for adding functions or equipment are needed.
The above-described publication JP 2000-69046 tries to apply the concept of wired packet transmission disclosed in ANSI/IEEE Std. 802 to a wireless packet network, and a single transmission tree is used in a wireless network, as illustrated in FIG. 2. In this example, a tree indicated by the bold arrows extends from root Bridge “a”. When transmitting a packet from Station S, which currently exists under Bridge b, to Station D, which currently belongs to Bridge c, the packet is transmitted through Bridge x7, Bridge x8, Bridge a, Bridge x3, and Bridge X4 along the route indicated by the dashed arrow. With this configuration, problems of route redundancy and concentration of load arise.
With the technique disclosed in JP 2000-78147A, the packet transmission route can be shortened by monitoring at a node those packets approaching that node. However, load concentration occurs at the root bridge of the transmission tree. Consequently, the entire network efficiency is lowered.
In the packet transmission system disclosed in JP 2003-188811, the determination whether to establish a channel between adjacent wireless basestations is made based on the power level of the received signal. However, the actual wireless communication environment changes easily, and wireless interfaces that adaptively change the communication rates according to the environment are also used. The technique shown in this publication cannot estimate the link cost reflecting the communication rate. Consequently, the throughput of the network is lowered as a whole, and the network connectivity is degraded.
The route optimization method disclosed in JP 2003-152786A considers the change in the wireless environment. However, it does not consider overhead with respect to the data transmission time, which overhead changes depending on the size (or the length) of the payload of a packet.
With the conventional packet transmission methods in the third layer (the network layer), wireless devices not having bridging functions cannot participate in the network. On the other hand, packet transmission methods using bridges in the media access control (MAC) layer are still in the process of development for application to wireless networks. When using a transmission tree in a wireless network, localized load concentration cannot be avoided.